package com.atguigu.dijkstra;

import java.util.Arrays;

/**
 * @author RuiKnag
 * @create 2021-06-29-19:19
 */
/*
* 迪杰斯特拉算法时典型的最短路径算法，用于计算一个节点到其他节点的最短路径。它的主要特点时以起始点为中心向外层扩散，直到扩展到他的终点
*
*算法过程
* 设置出发点v，顶点集合V{v1,v2,v3,...},v到V中各个顶点的距离构成距离集合Dis，Dis{d1,d2,d3,...},Dis集合记录着v到图中各个顶点的距离，
* 到自身的距离看作0
*
*   从Dis选择最小的di并移除Dis集合，同时移除V集合中对应的顶点vi 此时v到Vi即为最短路径
*
*   更新Dis集合，更新规则，比较v到V集合中顶点的距离值，与v通过vi到V集合中顶点的距离值，保留值较小的一个，同时也应该更新顶点的
*   前驱节点为vi，表明是通过vi到达的。
*
*   重复执行这两个步骤，直到最短路径顶点为目标定点即可结束。
*
*
* */
public class DijkstraAlgorithm {
    public static void main(String[] args) {
        char[] vertex={'A','B','C','D','E','F','G'};
        //邻接矩阵
        final int N=65535;
        int[][] matrix={
                {N,5,7,N,N,N,2},
                {5,N,N,9,N,N,3},
                {7,N,N,N,8,N,N},
                {N,9,N,N,N,4,N},
                {N,N,8,N,N,5,4},
                {N,N,N,4,5,N,6},
                {2,3,N,N,4,6,N}

        };
        GGraph graph = new GGraph(vertex, matrix);
        graph.showGraph();
        graph.dijkstra(6);
        graph.showdijkstra();

    }
}
class VisitedVeryex{
    //记录各个定点是否被访问过 1，0
    public int[] aready_arr;
    //每个下标对应值为前一个顶点的下标
    public int[] pre_visited;
    //记录出发顶点到其他顶点的距离比如G为出发点，就会记录G到其他顶点的距离会动态更新
    public int[] dis;
    //构造器
    public VisitedVeryex(int length,int index){
        //length 表示顶点的个数
        this.aready_arr=new int[length];

        //index表示出发顶点的下标
        this.pre_visited=new int[length];
        this.dis=new int[length];
        //初始化dis数组
        Arrays.fill(dis,65535);
        this.dis[index]=0;
        //出点顶点为1
        this.aready_arr[index]=1;
    }
    //判断index是否被访问过 访问过 true 否则false
    public boolean in(int index){
        return aready_arr[index]==1;
    }
    //跟新出发顶点到index顶点的距离
    public void updateDis(int index,int len){
        dis[index]=len;
    }
    //更新顶点的前驱
    public void updatePre(int pre,int index){
        pre_visited[pre]=index;
    }
    //返回出发顶点到index顶点的距离
    public int getDis(int index){
        return dis[index];
    }
    //继续选择并返回新的访问顶点，比如这里G之后，就是A
    public int updateArr(){
        int min=65535;
        int index=0;
        for (int i = 0; i < aready_arr.length; i++) {
            if(aready_arr[i]==0&&dis[i]<min){
                min=dis[i];
                index=i;
            }
        }
        aready_arr[index]=1;
        return index;
    }
    //显示最后结果
    public void show(){
        System.out.println("+++++++++++++++++++++++++++++");
        //输出aready_arr
        for (int i: aready_arr
             ) {
            System.out.print(i+" ");
        }
        System.out.println();
        
        //输出pre_visited
        for (int i :pre_visited
             ) {
            System.out.print(i+" ");

            
        }
        System.out.println();
        //输出dis
        for (int i: dis
             ) {
            System.out.print(i+" ");
        }
        System.out.println();
        //为了好看
        char[] vertex={'A','B','C','D','E','F','G'};
        int count=0;
        for (int i: dis
        ) {
            if(i!=65535){
                System.out.print(vertex[count]+"("+i+")");
            }
            count++;
        }
    }

}

class GGraph{
    private char[] vertex;//顶点数组
    private int[][] matrix;//邻接矩阵
    private VisitedVeryex vv;

    public GGraph(char[] vertex, int[][] matrix) {
        this.vertex = vertex;
        this.matrix = matrix;
    }
    //显示最终结果
    public void showdijkstra(){
        vv.show();
    }
    //显示图的方法
    public void showGraph(){
        for (int[] link: matrix
        ) {
            System.out.println(Arrays.toString(link));

        }
    }
    //出发顶点的下标
    public void dijkstra(int index){
        vv = new VisitedVeryex(vertex.length, index);
        update(index);

        for (int i = 0; i < vertex.length; i++) {
            index=vv.updateArr();//
            update(index);
        }
    }
    //更新index下标顶点到周围顶点的距离和周围顶点的前驱节点
    public void update(int index){
        int len=0;
        for (int i = 0; i < matrix[index].length; i++) {
            len=vv.getDis(index)+matrix[index][i];
            if(!vv.in(i)&&len<vv.getDis(i)){
                vv.updatePre(i,index);
                vv.updateDis(i,len);
            }
        }
    }
}




